import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/12 15:57
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        solution.medianSlidingWindow(nums, 3);
    }

    private List<Integer> window;

    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] ans = new double[n - k + 1];
        window = new ArrayList<>();
        int left = 0;
        for (int right = 0; right < n; right++) {
            insert(nums[right]);
            if (window.size() == k) {
                if (k % 2 == 0) {
                    ans[left] = (double) window.get(k / 2 - 1) / 2 + (double) window.get(k / 2) / 2;
                } else {
                    ans[left] = window.get(k / 2);
                }
                remove(nums[left]);
                left++;
            }
        }
        return ans;
    }

    private void insert(int val) {
        int left = 0;
        int right = window.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (window.get(mid) < val) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        window.add(left, val);
    }

    private void remove(int val) {
        int left = 0;
        int right = window.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (window.get(mid) < val) {
                left = mid + 1;
            } else if (window.get(mid) > val) {
                right = mid - 1;
            } else {
                window.remove(mid);
                return;
            }
        }
    }
}
